package dongtaiguihua;

public class climbStair {

    public static int[] memo;

    public static void main(String[] args) {
        int n = 9;
        memo = new int[n + 1];
        System.out.println(dfs(n));
    }

    public static int dfs(int n){
        if(n <= 1) return 1;
        if(memo[n] != 0 ) return memo[n];
        memo[n] = dfs(n-1)+dfs(n-2);
        return memo[n];
    }
}
